#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int upper_bound(vector<int>& nums, int low, int high, int target){
        if(high <= low)return high;
        int mid;
        while(low < high){
            mid = (low + high) / 2;
            if(nums[mid] <= target)low = mid + 1;
            else if(nums[mid] > target)high = mid;
        }
        return high;
    }

    int lower_bound(vector<int>& nums, int low, int high, int target){
        if(high <= low)return high;
        int mid;
        while(low < high){
            mid = (low + high) / 2;
            if(nums[mid] < target)low = mid + 1;
            else if(nums[mid] >= target)high = mid;
        }
        return high;
    }
    
    int search(vector<int>& nums, int target) {
        return upper_bound(nums, 0, nums.size(), target) - lower_bound(nums, 0, nums.size(), target);
    }
};
/**
 * 2021.10.7
 * 两月后重写
 * 自己实现 lower_bound 和 upper_bound
 */


// class Solution {
// private:
// 	int low_bound(vector<int>& nums, int target){
//         if(!nums.size())return 0;
//         if(nums[nums.size() - 1] < target)return nums.size();
// 		int low = 0, high = nums.size(), mid;
// 		while(low < high){
// 			mid = (low + high) / 2;
// 			if(nums[mid] >= target && (!mid || nums[mid - 1] < target))return mid;
// 			else if(nums[mid] >= target)high = mid;
// 			else low = mid + 1;
// 		}
// 		return -1;
// 	} 
// 	int up_bound(vector<int>& nums, int target){
//         if(!nums.size())return 0;
//         if(nums[nums.size() - 1] <= target)return nums.size();
// 		int low = 0, high = nums.size(), mid;
// 		while(low < high){
// 			mid = (low + high) / 2;
// 			if(nums[mid] > target && (!mid || nums[mid - 1] <= target))return mid;
// 			else if(nums[mid] > target)high = mid;
// 			else low = mid + 1;
// 		}
// 		return -1;
// 	}
// public:
//     int search(vector<int>& nums, int target) {
//         return up_bound(nums, target) - low_bound(nums, target);
//     }
// };
// //2021.7.16
